Title:             Digital Signatures for Consensus
Authors:           Sergey Gorbunov; Hoeteck Wee

Abstract:
Multi-signatures enable a group of signers to jointly generate a short
and efficiently verifiable signature on a common message. They are
commonly used in proof-of-stake and permissioned blockchains, where
reaching consensus usually involves a committee of nodes signing the
next block. Adaptive corruptions, however, pose a common threat to
such designs, because the adversary can corrupt committee members
after they certified a block (and possibly after they sold their
stake) and use their signing keys to fork the chain by certifying a
different block, thereby undermining the main security goal of a
blockchain. Forward-secure signatures protect against such attacks by
letting signers evolve their keys over time, while keeping the
verification key constant. We present *Pixel*, a pairing-based
forward-secure multi-signature scheme optimized for use in
blockchains, that achieves substantial savings in bandwidth, storage
requirements, and verification effort. Pixel signatures consist of two
group elements, regardless of the number of signers, and can be
verified using three pairings and one exponentiation; they also
support non-interactive aggregation of individual signatures into a
multi-signature. We prove our scheme secure in the random-oracle model
under a suitable variant of the bilinear Diffie-Hellman inversion
problem.